\documentclass[10pt,a4paper]{article}
\usepackage{graphicx}
\usepackage{amsmath, amsthm, amssymb} 
\usepackage{amsfonts}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=cyan]{hyperref}
\usepackage[all]{hypcap}
\usepackage{url}
\usepackage{array}
%\usepackage{fancyhdr}
%\usepackage{titlesec}

\newtheorem{thm}{Theorem}[subsection]
\renewcommand{\thethm}{\arabic{subsection}.\arabic{def}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{\baselineskip}

\setlength{\topmargin}{-1cm}
\setlength{\oddsidemargin}{0cm}

\setlength{\textheight}{24cm}
\setlength{\textwidth}{16cm}

\hyphenchar\font=-1

%\pagestyle{fancy}
%\fancyhf{}
%\renewcommand{\headrulewidth}{0.4pt}
%\titlespacing{\subsubsection}{0pt}{*2}{*-2} %can change this to control white space between titles

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Title Page
\author{\textbf{Final Year Individual Project Report}\\
\textbf{Supervisor}: Dr. Paolo Cascini\\(\url{p.cascini@imperial.ac.uk})\\ \\
Department of Mathematics,\\ Imperial College London \\ 
}
\title{\emph{RSA Encryption}}
\begin{document}
\maketitle
\begin{center}
Ying Siu Liang\\
CID 00555452\\
(\url{ysl208@imperial.ac.uk}) \\
This is entirely my own work unless otherwise stated.
\end{center}

write names with capital or not\\
public-key with dash\\
apostrophes missing\\
give lots of (own) examples \\

\newpage
%%% Acknowledgements %%%
%\begin{center}\input{acknowledgements.tex}\end{center}

\newpage
%%% ABSTRACT %%%
%\begin{center}\input{abstract.tex}\end{center}
\section{Abstract}
Over the past few decades cryptography has set foot in/found its many uses in computer and communication systems, such as infrastructures and security services, and became an integral part of information protection.

%\fancyhead[R]{\textit{\leftmark}}
%\fancyfoot[C]{\thepage}
\newpage
\setcounter{tocdepth}{2}	
\tableofcontents
\newpage

%%% INTRODUCTION TO THE PROBLEM%%%
%\input{introduction.tex}
\section{Introduction}
\label{Introduction}
Cryptography is the practice of techniques used for information security to ensure data confidentiality, integrity and authentication. Discovered around 4000 years ago by the Egyptians, it has undergone several stages of improvements and developments in the twentieth century and hence revolutionlised secure communication around the world. It is used by many financial institutions for securing electronic commerce and has become an integral part of information protection for computer systems, infrastructures and security services.

In this paper we will discuss the two basic types of cryptographic systems, symmetric-key and public key cryptography (while focusing on the latter), and introduce practical encryption schemes, such as RSA and ElGamal, that have been developed over the past few decades.

Authentication/Identification 1.7.
\section{Background}
\label{Background}
In this chapter we will introduce different algorithms which are used in the cryptosystems that we discuss in this paper. The steps for the algorithms were inspired by \ref{handbook} and \ref{elliptic} as well as M3P14 lectures.

\subsection{Euclidean Algorithm}
\label{Euclidean Algorithm}
Given integers $a$ and $b$ we want to find the greatest common divisor $\gcd(a,b) = d$. The Euclidean algorithm provides an efficient way to find this number $d$ and consists of the simple steps below:
\begin{enumerate}
\item Without loss of generality, let $a>b$. Find $q$ and $r<b$ such that $a = bq + r$.
\item If $r \neq 0$ set $a = b$ and $b = r$ and go back to Step 1;
\item Else return $b$.
\end{enumerate}

\emph{Example.}\\
Calculate the greatest common divisor of $a = 1214$ and $b = 3534$. Following the algorithm above, results in the following steps:
\begin{align*}
3534 &= 1214 \cdot 2 + 1106\\
1214 &= 1106 \cdot 1 + 108 \\
1106 &= 108 \cdot 10 + 26 \\
108 &= 26 \cdot 4 + 4 \\
26 &= 4 \cdot 6 + 2 \\
4 &= 2 \cdot 2.
\end{align*}
So $\gcd(1214,3534) = 2$.

\subsection{Extended Euclidean Algorithm}
\label{Extended Euclidean Algorithm}
The Euclidean algorithm can be extended to find integers $x$ and $y$ such that $ax + by = d$ and consists of the following steps:
\begin{enumerate}
\item Find $r_0$ and $q_0$

\end{enumerate}•

\emph{Example.}

\subsection{Modular Multiplicative Inverses}%\ref{handbook}
\label{Multiplicative Inverses}
Given integers $a$ and $m$ we want to find integer $x$ such that $a^{-1} \equiv x \mod m$, $x$ is then called the multiplicative inverse of $a$ modulo $m$. However, $x$ only exists if and only if $a$ and $m$ are coprime, i.e. $\gcd(a,m) = 1$. The steps to find $x$ are the following:
\begin{enumerate}
\item Find $x, y$ and $d$ such that $ax + my = d$ using the extended Euclidean algorithm.
\item If $d \neq 1$ then there exist no multiplicative inverse;
\item else return $x$

\end{enumerate}

\emph{Proof.} \\
If $\gcd(a,m) = 1$ then there exist $x$ and $y$ such that $ax + my = 1$. This means that $ax \equiv 1 \equiv aa^{-1} \mod m$ so $x \equiv a^{-1} \mod m$.

\section{Symmetric Key Cryptography}
\label{symmetric}
 Let $E_e$ be an encryption transformation for key $e \in K$ and $D_d$ be a decryption transformation for key $d \in K$. If it is computationally feasible to determine $d$ given only $e$, and vice versa, then the encryption scheme is said to be \textit{symmetric-key}.~\cite{handbook}

In many cases $e=d$ which is why the name symmetric-key was derived. Popular symmetric-key encryption methods are Data Encryption Standard (DES) and the Advanced Encryption Standard (AES).

A communication between two parties A and B using symmetric-key cryptography would work as follows: A selects a key pair $(e,d)$ and informs B about $d$ over a secured channel. A then sends an encrypted message using $E_e$ to B with only B being able to decrypt the message using the decryption transformation $D_d$.

We will illustrate the use of symmetric keys with an example:

\subsection{Example}

When using symmetric keys the \textit{key distribution problem} is encountered which encompasses the issue of finding an efficient method to exchange keys securely.

Symmetric-key encryption distinguishes two encryption schemes: \textit{block ciphers} and \textit{stream ciphers}.

\section{Public Key Cryptography}
\label{public}
public key encryption, also known as asymmetric encryption, was introduced in 1976 by Diffie and Hellman.

Let $E_e$ be an encryption transformation for key $e \in K$ and $D_d$ be a decryption transformation for key $d \in K$. If it is computationally infeasible to determine $d$ given only $e$, then the encryption scheme is said to be \textit{public key}.

A communication between two parties A and B using public key cryptography works as follows: A selects a key pair $(e,d)$ and makes the encryption key $e$ public but keeps the decryption key $d$ private. B can now send A an encrypted message $m$ by applying the encryption transformation $E_e(m) = c$ and A can decrypt $c$ by using the decryption transformation $D_d(c) = m$.

Note that if A is the only one who holds the decryption key $d$ and B destroys the original message $m$, then B will not be able to decrypt message $c$ without knowing $D_d$.

Since the encryption key $e$ is public, this would mean that anybody could send an encrypted message to A. In order for A to know that a message is delivered from B and not by someone else, A and B need to conduct some form of data origin authentication.

A selects a key pair $(e,d)$ and B selects a key pair $(f,g)$. A makes their encryption key public but keeps the decryption key private. Now B encrypts their decryption key $g$ using A’s encryption transformation $E_e$ and sends it back to A. A has now B’s decryption key. If A repeats the same procedure with their decryption key $d$ then both A and B can have each other’s encryption and decryption keys. A and B can now agree on a secret password that they will use for any messages sent. For any future communication, A and B encrypt their messages together with the secret password and so they will always know if a message is actually sent by the other party.


\subsection{Public key in Comparison to Symmetric-key}
\label{public vs symmetric}
public key
key to describe public verification function is much smaller 
public/private key pair can remain unchanged for a several periods of time
hence, the number of keys necessary is considerably smaller
inferior computational performance, slower throughput rates for most p-k encryption methods
p-k: efficient signatures and key management
s-k: efficient for encryption and data integrity applications

\subsection{The Discrete Logarithm Problem} %\ref{handbook} and \ref{elliptic}
\label{DLP}
The discrete logarithm problem has found its use in many public key cryptosystems, such as ElGamal (which will be discussed later in Chapter \ref{elgamal}), and proved that the more difficult it is to solve the discrete logarithm problem, the more security it provides.

The problem is as follows:

Given prime $p$ and integers $a, b$ non-zero mod $ p$, find an integer $k$ such that $a^k \equiv b$ (mod $p$).

We can define this problem more generally in terms of a multiplicative cyclic group $G$:

The element $a \in G$ is the generator for $G$ if we can find an integer $k$ for any element $b \in G$ such that $a^k = b$. Let $N$ be the order of the group $G$ which is the smallest integer $n$ for which $a^n = 1$. The discrete logarithm problem is to find a number $k$ such that $a^k = b$ when given $a, b$.

Besides simply using brute force by trying all possible values of $k$, there are many other ways to approach the discrete logarithm problem and we will now introduce some methods which are useful for elliptic curves.

(Index calculus)

\subsubsection{Shanks' Baby-Step Giant-Step approach}
\label{shanks}
This method was originally developed by Daniel Shanks and works for arbitrary finite cyclic groups. It requires about $\sqrt{N}$ steps and $\sqrt{N}$ storage and is generally used for groups whose order is prime.\ref{babygiantwiki}

The algorithm works as follows:
\begin{enumerate}
\item Let $m = \lceil \sqrt{N}\rceil$.
\item Baby Step: Compute and store a list of ($a^i,i$) for $0< i \leq m$. If any $a^i = 1$, then return $k = i$.
\item Giant Step: Compute $b a^{-jm}$ for $j = 1, \dots m-1$. If any matches an element from the stored list in Step 2, return $k = jm+i$.
%\item If $a^i = b / a^{jm}$, we have $b = a^k$ with $k \equiv i + jm$ (mod $N$).
\end{enumerate}

\emph{Proof}\\
The algorithm is based on rewriting $k = jm + i$ so that we have $b(a^{-m})^j = a^i$. \ref{babygiantwiki} From Step 1 we can deduce that $m^2>N$ and since $k < N$ we have that $k < m^2$. It is possible to find unique $0\leq k_0 <m and k_1$ such that $k = k_0 + mk_1$. Then $k_1 = (k-k_0)/m < m$. From Steps 2 and 3 we have $i$ and $j$ so set $i = k_0$ and $j = k_1$. Thus, we have $ba^{-k_1m} = a^ka^{-k_1m} = a^{k-k_1m} = a^{k_0}$ so there is a match.

We dont need to know the exact order $N$ of $G$ but an upper bound would suffice. 

%Since $a^k = b$ we have that $a^i = a^{-jm}$ if and only if $jm + i$ is a multiple of $k$. If $k \leq m$, then we find the right $k$ using the Baby Step. Otherwise, if $k > m$, we use the Giant Step to find the smallest $k = jm+i$ such that $1\leq i \leq m$ for which $a^i = a^{-jm}$.\ref{sutherland}

\emph{Example.}\\
We want to find $k$ such that $3^k \equiv 37 \mod 101$. We follow the above steps:
\begin{enumerate}
\item Define $m = \lceil \sqrt{100}\rceil = 10$.
\item Baby Step: Compute ($3^i,i$) and get the following list: \newline
\begin{center}
\begin{tabular}{|c || c| c| c| c| c| c| c| c| c| c| c| }
\hline
  \bf{i} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\hline
 \bf{$3^i$} & 1 & 3 & 9 & 27 & 81 & 41 & 22 & 66 & 97 & 89 & 65 \\
\hline
\end{tabular}
\end{center}
\item Giant Step: In order to compute $b a^{-jm}$, we need to compute $3^-1 \mod 101$ first. We can find this by calculating $3x \equiv 1 \mod 101$ using Euclid`s Algorithm and get $x = 34$. So $3^-1 \equiv 34 \mod 101$ and hence $3^{-im} \equiv (3^{-1})^{im} \mod 101$. \newline
\begin{center}
\begin{tabular}{|c || c| c| c| c| c| c| c| c| c| c| c| }
\hline
  \bf{j} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
 \bf{$3^{-jm}$} & 72 & 33 & 53 & 79 & 32 & 82 & 46 & 80 & 3 & 14  \\
\hline
 \bf{$37 \cdot \dot 3^{-jm}$} & 38 & 9 & 42 & 95 & 73 & 4 & 86 & 31 & 10 & 13 \\
\hline
\end{tabular}
\end{center}
We can see that for $i = 2$ and $j = 2$ the elements match and hence we have $k = 2\cdot 11 + 2 = 24$ for which we have indeed $3^{24} \equiv 37 \mod 101$.
\end{enumerate}

The Baby-Step Giant-Step algorithm requires a lot of storage so we will now discuss another method which is an improvement.

\subsubsection{Pollard's $\rho$ and $\lambda$ method}
\label{pollard}
runs in same time but little storage


\subsubsection{Pohlig-Hellman}
\label{pohlig}
uses the Chinese Remainder Theorem


%\ref{elliptic}

%%% ELLIPTIC CURVES %%%
%\input{elliptic.tex}
\subsection{Elliptic Curves}
\label{elliptic curves}
Many cryptosystems are based on elliptic curves as they provide a more efficient way of implementing security by using fewer bits. In this section we will introduce well-known public key systems that use elliptic curves to establish keys that are used in symmetric key systems.

Equations for Elliptic Curves
Weierstrass: $y^2 = x^3 + Ax + B$ where $A$ and $B$ are constants. \\
Legendre Equation \\
Torsion Points: Elements which have finite order\\
The Weil Pairing\\

% Elliptic Curve Cryptography

\subsection{Diffie-Hellman Problem}

\subsection{ElGamal Encryption}
\label{elgamal}



\subsection{RSA Encryption}
\label{RSA Encryption}
   - Digital Signatures
   - Computing Individual Bits
 - Knapsack Problem

\section{Discussion of the Results}

\section{Conclusion}

\newpage
%%% APPENDIX %%%
\appendix

\input{appendix.tex}

\end{document}
